import random
import time
import sys
sys.setrecursionlimit(1000000)

class Sort:
    def __init__(self, n):
        #self.arr = [0]*n
        self.len = n
        self.arr = [0]*n
        self.random_data()

    def random_data(self):
        for i in range(self.len):
             self.arr[i] = random.randint(0,99)

    def partition(self,left,right):
        arr = self.arr
        k = i =left
        random_pos = random.randint(left, right)  # 如何避免陷入最坏时间复杂度
        arr[random_pos], arr[right] = arr[right], arr[random_pos]
        for i in range(left,right):
            if arr[i]<arr[right]:
                arr[i],arr[k] = arr[k],arr[i] #交换
                k+=1
        arr[k],arr[right] = arr[right],arr[k]
        return k


    def quick_sort(self,left,right):
        if left < right:
            pivot = self.partition(left,right)
            self.quick_sort(left,pivot-1)
            self.quick_sort(pivot+1,right)

    def adjust_max_heap(self ,pos,arr_len):
        arr = self.arr
        dad = pos
        son = dad*2+1
        while son < arr_len:
                if son+1 < arr_len and arr[son]<arr[son+1]:
                    son += 1
                if arr[son] > arr[dad]:
                    arr[son],arr[dad] = arr[dad],arr[son]
                    dad = son
                    son = dad*2+1
                else:
                    break
    def heap_sort(self):
        for parent in range(self.len // 2 - 1, -1, -1):
            self.adjust_max_heap(parent, self.len)
        arr = self.arr
        arr[0],arr[self.len-1] = arr[self.len-1],arr[0]
        for arr_len in range(self.len -1 ,1,-1):
            self.adjust_max_heap(0,arr_len)
            arr[0],arr[self.len-1] = arr[self.len-1],arr[0]


    def test_time_use(self,sort_func,*args,**kwargs):
        start = time.time()
        sort_func(*args,**kwargs)
        end = time.time()
        print(f"总用时{end - start}")




if __name__ == '__main__':
    my_sort = Sort(10)
    print(my_sort.arr)
    my_sort.quick_sort(0,9) # 调用快速排序
    print(my_sort.arr)
    my_sort.heap_sort()
    my_sort.test_time_use(my_sort.heap_sort)
    print(my_sort.arr)




"""c语言模版
void quick_sort(int arr[],int l,int r){
        int i = l-1,j = r+1,x = arr[i+j>>1]
        while(i>j)  return
        while(i<j){
           do i++ while(arr[i]<x)
           do j-- while(arr[j]>x)
           if(i<=j) swap(arr[i],arr[j])
        }
        quick_sort(arr,l,j)
        quick_sort(arr,j+1,r)
}"""